{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Circus Tower LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #dynamic-programming #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #动态规划 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: bestSeqAtIndex"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #马戏团人塔"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有个马戏团正在设计叠罗汉的表演节目，一个人要站在另一人的肩膀上。出于实际和美观的考虑，在上面的人要比下面的人矮一点且轻一点。已知马戏团每个人的身高和体重，请编写代码计算叠罗汉最多能叠几个人。</p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>height = [65,70,56,75,60,68] weight = [100,150,90,190,95,110]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>从上往下数，叠罗汉最多能叠 6 层：(56,90), (60,95), (65,100), (68,110), (70,150), (75,190)</pre>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>height.length == weight.length <= 10000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [circus-tower-lcci](https://leetcode.cn/problems/circus-tower-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [circus-tower-lcci](https://leetcode.cn/problems/circus-tower-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[65,70,56,75,60,68]\\n[100,150,90,190,95,110]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        hw = sorted(zip(height, weight))\n",
    "        \n",
    "        dp = [] # dp[i]: 长度为(i+1)的(height, weight)双严格上升子序列中，末尾的weight最小是多少\n",
    "        temp = []\n",
    "        for i in range(len(hw)):\n",
    "            # temp: 记录(要填入的体重, 要填入的位置)\n",
    "            temp.append((hw[i][1], bisect.bisect_left(dp, hw[i][1])))\n",
    "\n",
    "            # 到达尽头或下一个height严格变大时，开始填入\n",
    "            if i == len(hw) - 1 or hw[i][0] < hw[i+1][0]:\n",
    "                for w, i in temp:\n",
    "                    # 添加到dp末尾\n",
    "                    if i == len(dp):\n",
    "                        dp.append(w)\n",
    "                    # 更新dp[i]；注意同一height下weight是递增的，所以不能直接赋值，要取较小者\n",
    "                    else:\n",
    "                        dp[i] = min(dp[i], w)\n",
    "                temp = []\n",
    "        return len(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        l = []\n",
    "        for i in range(len(height)):\n",
    "            l.append([height[i],weight[i]])\n",
    "        l = sorted(l,key = lambda x:(x[0],-x[1]))\n",
    "        count = [0*i for i in range(len(l))]\n",
    "        dp = []\n",
    "        nums = [i[1] for i in l]\n",
    "        for i in range(len(l)):\n",
    "            if not dp or l[i][1] > dp[-1]:\n",
    "                dp.append(nums[i])\n",
    "            m = 0\n",
    "            n = len(dp) - 1\n",
    "            while m <= n:\n",
    "                mid = (m+n)>>1\n",
    "                if dp[mid] >= nums[i]:\n",
    "                    n = mid - 1\n",
    "                else:\n",
    "                    m = mid + 1\n",
    "            if m <len(dp):\n",
    "                dp[m] = nums[i]\n",
    "        print(dp)\n",
    "        return len(dp)\n",
    "\n",
    "        # li = []\n",
    "        # for i, j in zip(height, weight):\n",
    "        #     li.append([i,j])\n",
    "        # li.sort(key = lambda x:(x[0],-x[1]))\n",
    "\n",
    "        # nums = [i[1] for i in li]\n",
    "        # dp = []\n",
    "        # for i in range(len(nums)):\n",
    "        #     # 如果新数比末尾数大，直接append\n",
    "        #     if not dp or nums[i]>dp[-1]:\n",
    "        #         dp.append(nums[i])\n",
    "        #     # 如果新数没有末尾数大，寻找第一个比新数小的数d[k]，并更新d[k+1] = nums[i]\n",
    "        #     left, right = 0, len(dp)-1\n",
    "        #     while left <= right:\n",
    "        #         mid = (left + right) // 2\n",
    "        #         if dp[mid] >= nums[i]:\n",
    "        #             right = mid - 1\n",
    "        #         else:\n",
    "        #             left = mid + 1\n",
    "        #     if left < len(dp):\n",
    "        #         dp[left] = nums[i]\n",
    "\n",
    "        # return len(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        li = []\n",
    "        for i, j in zip(height, weight):\n",
    "            li.append([i,j])\n",
    "        li.sort(key = lambda x:(x[0],-x[1]))\n",
    "\n",
    "        nums = [i[1] for i in li]\n",
    "        dp = []\n",
    "        print(li)\n",
    "        print(nums)\n",
    "        for i in range(len(nums)):\n",
    "            # 如果新数比末尾数大，直接append\n",
    "            if not dp or nums[i]>dp[-1]:\n",
    "                dp.append(nums[i])\n",
    "            # 如果新数没有末尾数大，寻找第一个比新数小的数d[k]，并更新d[k+1] = nums[i]\n",
    "            left, right = 0, len(dp)-1\n",
    "            while left <= right:\n",
    "                mid = (left + right) // 2\n",
    "                if dp[mid] >= nums[i]:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid+1\n",
    "            print\n",
    "            if left < len(dp):\n",
    "                dp[left] = nums[i]\n",
    "\n",
    "        return len(dp)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    import bisect\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:       \n",
    "       dp=[]\n",
    "       for a,b in sorted(zip(height,weight),key = lambda x:[x[0],-x[1]]):\n",
    "           pos = bisect.bisect_left(dp,b)\n",
    "           dp[pos:pos+1] = [b]\n",
    "       return len(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        arr = []\n",
    "        for i in range(len(height)):\n",
    "            arr.append([height[i], weight[i]])\n",
    "        arr.sort(key=lambda x: [x[0],-x[1]])\n",
    "        # f[i] 表示长度为i的子序列的最小值\n",
    "        f = []\n",
    "        for v in arr:\n",
    "            weight = v[1]\n",
    "            height = v[0]\n",
    "            index = bisect.bisect_left(f, [weight,0])\n",
    "            if index>0 and height<=f[index-1][1]:\n",
    "                continue\n",
    "            if index == len(f):\n",
    "                f.append([weight,height])\n",
    "            else:\n",
    "                if weight==f[index][0]:\n",
    "                    continue\n",
    "                f[index] = [weight,height]\n",
    "        return len(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        newList = list()\n",
    "        for i in range(len(height)):\n",
    "            newList.append([height[i], weight[i]])\n",
    "        newList.sort(key=lambda x:[x[0], -x[1]])\n",
    "        dp = list()\n",
    "        for i in range(len(newList)):\n",
    "            if not dp or newList[i][1] > dp[-1][1]:\n",
    "                dp.append(newList[i])\n",
    "            else:\n",
    "                l = 0\n",
    "                r = len(dp) - 1\n",
    "                while l < r:\n",
    "                    mid = (r + l) // 2\n",
    "                    if newList[i][1] <= dp[mid][1]:\n",
    "                        r = mid\n",
    "                    else:\n",
    "                        l = mid + 1\n",
    "                dp[l] = newList[i]\n",
    "        return len(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, h: List[int], w: List[int]) -> int:\n",
    "        nums=[]\n",
    "        n=len(h)\n",
    "        for a,b,i in zip(h,w,range(n)):\n",
    "            nums.append([a,b,i])\n",
    "        #转换成(身高，体重，下标)的三元组\n",
    "        \n",
    "        nums.sort(key=lambda x:(x[0],-x[1]))\n",
    "        #按身高升序，体重降序进行排序\n",
    "        \n",
    "        tail=[]  #最长上升子序列\n",
    "        for a,b,i in nums:\n",
    "            if not tail or b>tail[-1]: \n",
    "                tail.append(b)\n",
    "            else:\n",
    "                x=bisect_left(tail,b)#找到tail中第一个大于b的数\n",
    "                tail[x]=b  #替换\n",
    "                \n",
    "        return len(tail)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        hw = sorted(zip(height,weight))\n",
    "        dp=[]\n",
    "        temp=[]\n",
    "        for i in range(len(hw)):\n",
    "            temp.append((hw[i][1],bisect.bisect_left(dp,hw[i][1])))\n",
    "            if i==len(hw)-1 or hw[i][0]<hw[i+1][0]:\n",
    "                for w,i in temp:\n",
    "                    if i==len(dp):\n",
    "                        dp.append(w)\n",
    "                    else:\n",
    "                        dp[i]=min(dp[i],w)\n",
    "                temp=[]\n",
    "        return len(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        hw = sorted(zip(height,weight))\n",
    "        dp=[]\n",
    "        temp=[]\n",
    "        for i in range(len(hw)):\n",
    "            temp.append((hw[i][1],bisect.bisect_left(dp,hw[i][1])))\n",
    "            if i == len(hw)-1 or hw[i][0] < hw[i+1][0]:\n",
    "                for w,i in temp:\n",
    "                    if i== len(dp):\n",
    "                        dp.append(w)\n",
    "                    else:\n",
    "                        dp[i]= min(dp[i],w)\n",
    "                temp=[]\n",
    "        return len(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        arr = []\n",
    "        for i in range(len(height)):\n",
    "            arr.append([height[i], weight[i]])\n",
    "        arr.sort(key=lambda x: [x[0],-x[1]])\n",
    "        # f[i] 表示长度为i的子序列的最小值\n",
    "        arr=[x[1] for x in arr]\n",
    "        f = []\n",
    "        for v in arr:\n",
    "            index = bisect.bisect_left(f, v)\n",
    "            if index == len(f):\n",
    "                f.append(v)\n",
    "            else:\n",
    "                f[index] =v\n",
    "        return len(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        newList = list()\n",
    "        for i in range(len(height)):\n",
    "            newList.append([height[i], weight[i]])\n",
    "        newList.sort(key=lambda x:[x[0], -x[1]])\n",
    "        dp = list()\n",
    "        for i in range(len(newList)):\n",
    "            if not dp or newList[i][1] > dp[-1][1]:\n",
    "                dp.append(newList[i])\n",
    "            else:\n",
    "                l = 0\n",
    "                r = len(dp) - 1\n",
    "                while l < r:\n",
    "                    mid = (r + l) // 2\n",
    "                    if newList[i][1] <= dp[mid][1]:\n",
    "                        r = mid\n",
    "                    else:\n",
    "                        l = mid + 1\n",
    "                dp[l] = newList[i]\n",
    "        return len(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        hw = sorted(zip(height, weight))\n",
    "        \n",
    "        dp = [] # dp[i]: 长度为(i+1)的(height, weight)双严格上升子序列中，末尾的weight最小是多少\n",
    "        temp = []\n",
    "        for i in range(len(hw)):\n",
    "            # temp: 记录(要填入的体重, 要填入的位置)\n",
    "            temp.append((hw[i][1], bisect.bisect_left(dp, hw[i][1])))\n",
    "\n",
    "            # 到达尽头或下一个height严格变大时，开始填入\n",
    "            if i == len(hw) - 1 or hw[i][0] < hw[i+1][0]:\n",
    "                for w, i in temp:\n",
    "                    # 添加到dp末尾\n",
    "                    if i == len(dp):\n",
    "                        dp.append(w)\n",
    "                    # 更新dp[i]；注意同一height下weight是递增的，所以不能直接赋值，要取较小者\n",
    "                    else:\n",
    "                        dp[i] = min(dp[i], w)\n",
    "                temp = []\n",
    "        return len(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        newList = list()\n",
    "        for i in range(len(height)):\n",
    "            newList.append([height[i], weight[i]])\n",
    "        newList.sort(key=lambda x:[x[0], -x[1]])\n",
    "        dp = list()\n",
    "        for i in range(len(newList)):\n",
    "            if not dp or newList[i][1] > dp[-1][1]:\n",
    "                dp.append(newList[i])\n",
    "            else:\n",
    "                l = 0\n",
    "                r = len(dp) - 1\n",
    "                while l <= r:\n",
    "                    mid = (r + l) // 2\n",
    "                    if newList[i][1] <= dp[mid][1]:\n",
    "                        loc = mid\n",
    "                        r = mid - 1\n",
    "                    else:\n",
    "                        l = mid + 1\n",
    "                dp[loc] = newList[i]\n",
    "        return len(dp)\n",
    "#1.先按照身高升序，体重排序将问题从二维问题变为一维升序问题\n",
    "#再参见leetcode 300题 https://leetcode-cn.com/problems/longest-increasing-subsequence/\n",
    "#2.二分或dp\n",
    "'''\n",
    "#dp[i] = max(dp[i], dp[j]xxx)\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        dp = []\n",
    "        for i in range(len(nums)):\n",
    "            dp.append(1)\n",
    "            for j in range(i):\n",
    "                if nums[i] > nums[j]:\n",
    "                    dp[i] = max(dp[i], dp[j] + 1)\n",
    "        return max(dp)\n",
    "#最小递增数组\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int]) -> int:\n",
    "        d = []\n",
    "        for n in nums:\n",
    "            if not d or n > d[-1]:\n",
    "                d.append(n)\n",
    "            else:\n",
    "                l, r = 0, len(d) - 1\n",
    "                loc = r\n",
    "                while l <= r:\n",
    "                    mid = (l + r) // 2\n",
    "                    if d[mid] >= n:\n",
    "                        loc = mid\n",
    "                        r = mid - 1\n",
    "                    else:\n",
    "                        l = mid + 1\n",
    "                d[loc] = n\n",
    "        return len(d)\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        d = defaultdict(list)\n",
    "        for h, w in zip(height, weight):\n",
    "            d[h].append(w)\n",
    "        a = []\n",
    "        for h in sorted(d):\n",
    "            d1 = defaultdict(lambda: inf)\n",
    "            for w in d.pop(h):\n",
    "                i = bisect_left(a, w)\n",
    "                d1[i] = min(d1[i], w)\n",
    "            for i, w in d1.items():\n",
    "                if i >= len(a):\n",
    "                    a.append(w)\n",
    "                    continue\n",
    "                a[i] = w\n",
    "        return len(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        newList = list()\n",
    "        for i in range(len(height)):\n",
    "            newList.append([height[i], weight[i]])\n",
    "        newList.sort(key=lambda x:[x[0], -x[1]])\n",
    "        dp = list()\n",
    "        for i in range(len(newList)):\n",
    "            if not dp or newList[i][1] > dp[-1][1]:\n",
    "                dp.append(newList[i])\n",
    "            else:\n",
    "                l = 0\n",
    "                r = len(dp) - 1\n",
    "                while l < r:\n",
    "                    mid = (r + l) // 2\n",
    "                    if newList[i][1] <= dp[mid][1]:\n",
    "                        r = mid\n",
    "                    else:\n",
    "                        l = mid + 1\n",
    "                dp[l] = newList[i]\n",
    "        return len(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        list1 = list(set(height))\n",
    "        list1.sort()\n",
    "        dic1 = {}\n",
    "        for i in list1:\n",
    "            dic1[i] = []\n",
    "        for i in range(len(height)):\n",
    "            dic1[height[i]].append(weight[i])\n",
    "\n",
    "        list2 = []\n",
    "        for i in list1:\n",
    "            list_ = dic1[i]\n",
    "            list_.sort()\n",
    "            list2 += list_[::-1]\n",
    "\n",
    "        list_num = [list2[0]]\n",
    "\n",
    "        for num in list2:\n",
    "            if num > list_num[-1]:\n",
    "                list_num.append(num)\n",
    "\n",
    "            elif num <= list_num[-1]:\n",
    "                for i in range(len(list_num)):\n",
    "                    if list_num[i] >= num:\n",
    "                        list_num[i] = num\n",
    "                        break\n",
    "\n",
    "        # return list2, list_num\n",
    "        # return list_num\n",
    "        return len(list_num)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        bound_data = sorted(zip(height, [-w for w in weight]))\n",
    "\n",
    "        ordered_weight = []\n",
    "        for i in range(len(bound_data)):\n",
    "            ordered_weight.append(-bound_data[i][1])\n",
    "\n",
    "        ret = 0\n",
    "        dp = []\n",
    "        for w in ordered_weight:\n",
    "            if len(dp) == 0 or w > dp[-1]:\n",
    "                ret += 1\n",
    "                dp.append(w)\n",
    "            else:\n",
    "                l, r = 0, len(dp) - 1\n",
    "                while l <= r:\n",
    "                    mid = l + (r - l) // 2\n",
    "                    if dp[mid] < w:\n",
    "                        l = mid + 1\n",
    "                    else:\n",
    "                        r = mid - 1\n",
    "                dp[l] = w\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        newList = list()\n",
    "        for i in range(len(height)):\n",
    "            newList.append([height[i], weight[i]])\n",
    "        newList.sort(key=lambda x:[x[0], -x[1]])\n",
    "        dp = list()\n",
    "        for i in range(len(newList)):\n",
    "            if not dp or newList[i][1] > dp[-1][1]:\n",
    "                dp.append(newList[i])\n",
    "            else:\n",
    "                l = 0\n",
    "                r = len(dp) - 1\n",
    "                while l <= r:\n",
    "                    mid = (r + l) // 2\n",
    "                    if newList[i][1] <= dp[mid][1]:\n",
    "                        loc = mid\n",
    "                        r = mid - 1\n",
    "                    else:\n",
    "                        l = mid + 1\n",
    "                dp[loc] = newList[i]\n",
    "        return len(dp)\n",
    "#先按照身高升序，体重降序排序将问题从二维问题变为一维问题\n",
    "#再参见leetcode 300题 https://leetcode-cn.com/problems/longest-increasing-subsequence/\n",
    "'''\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        dp = []\n",
    "        for i in range(len(nums)):\n",
    "            dp.append(1)\n",
    "            for j in range(i):\n",
    "                if nums[i] > nums[j]:\n",
    "                    dp[i] = max(dp[i], dp[j] + 1)\n",
    "        return max(dp)\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int]) -> int:\n",
    "        d = []\n",
    "        for n in nums:\n",
    "            if not d or n > d[-1]:\n",
    "                d.append(n)\n",
    "            else:\n",
    "                l, r = 0, len(d) - 1\n",
    "                loc = r\n",
    "                while l <= r:\n",
    "                    mid = (l + r) // 2\n",
    "                    if d[mid] >= n:\n",
    "                        loc = mid\n",
    "                        r = mid - 1\n",
    "                    else:\n",
    "                        l = mid + 1\n",
    "                d[loc] = n\n",
    "        return len(d)\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        people=list()\n",
    "        for i in range(len(height)):\n",
    "            people.append([height[i],weight[i]])\n",
    "        \n",
    "        people.sort(key=lambda x:[x[0],-x[1]])\n",
    "      \n",
    "        waitprocess=[]\n",
    "        for i in range(len(people)):\n",
    "            waitprocess.append(people[i][1])\n",
    "        \n",
    "        \n",
    "        \n",
    "        ans=[]\n",
    "        for n in waitprocess:\n",
    "            if not ans or n>ans[-1]:\n",
    "                ans.append(n)\n",
    "            else:\n",
    "                l,r=0,len(ans)-1\n",
    "                loc=0\n",
    "                while l<=r:\n",
    "                    mid=(l+r)//2\n",
    "                    if ans[mid]>=n:\n",
    "                        loc=mid\n",
    "                        r=mid-1\n",
    "                    else:\n",
    "                        l=mid+1\n",
    "                ans[loc]=n\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        newList = list()\n",
    "        for i in range(len(height)):\n",
    "            newList.append([height[i], weight[i]])\n",
    "        newList.sort(key=lambda x:[x[0], -x[1]])\n",
    "        dp = list()\n",
    "        for i in range(len(newList)):\n",
    "            if not dp or newList[i][1] > dp[-1][1]:\n",
    "                dp.append(newList[i])\n",
    "            else:\n",
    "                l = 0\n",
    "                r = len(dp) - 1\n",
    "                while l < r:\n",
    "                    mid = (r + l) // 2\n",
    "                    if newList[i][1] <= dp[mid][1]:\n",
    "                        r = mid\n",
    "                    else:\n",
    "                        l = mid + 1\n",
    "                dp[l] = newList[i]\n",
    "        return len(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        newList = list()\n",
    "        for i in range(len(height)):\n",
    "            newList.append([height[i], weight[i]])\n",
    "        newList.sort(key=lambda x:[x[0], -x[1]])\n",
    "        dp = list()\n",
    "        for i in range(len(newList)):\n",
    "            if not dp or newList[i][1] > dp[-1][1]:\n",
    "                dp.append(newList[i])\n",
    "            else:\n",
    "                l = 0\n",
    "                r = len(dp) - 1\n",
    "                while l < r:\n",
    "                    mid = (r + l) // 2\n",
    "                    if newList[i][1] <= dp[mid][1]:\n",
    "                        r = mid\n",
    "                    else:\n",
    "                        l = mid + 1\n",
    "                dp[l] = newList[i]\n",
    "        return len(dp)\n",
    "\n",
    "\n",
    "# 作者：miraking\n",
    "# 链接：https://leetcode.cn/problems/circus-tower-lcci/solution/by-miraking-28dz/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        n = len(height)\n",
    "        lst = list()\n",
    "        for i in range(n):\n",
    "            lst.append([height[i],weight[i]])\n",
    "        lst.sort(key = lambda lst:[lst[0],-lst[1]])\n",
    "        dp = list()\n",
    "        for i in range(n):\n",
    "            if not dp or dp[-1][1] < lst[i][1]:\n",
    "                dp.append(lst[i])\n",
    "            else:\n",
    "                l,r = 0,len(dp)-1\n",
    "                while l<r:\n",
    "                    m = (l+r)//2\n",
    "                    if dp[m][1] < lst[i][1]:\n",
    "                        l = m+1\n",
    "                    else:\n",
    "                        r = m\n",
    "                dp[l] = lst[i]\n",
    "        return len(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "先按照身高升序，体重降序排序将问题从二维问题变为一维问题\n",
    "然后问题就变成为在一堆体重序列中查找【最长递增子序列】的问题，\n",
    "然后此时可以使用【动态规划】解决问题，但是在这道题用动态规划会超时，\n",
    "所以改用【贪心+二分查找】的方法，不懂的小伙伴可以查看leetcode 300题【最长递增子序列】\n",
    "'''\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        newList = list()\n",
    "        for i in range(len(height)):\n",
    "            newList.append([height[i], weight[i]])\n",
    "        newList.sort(key=lambda x:[x[0], -x[1]])\n",
    "        dp = list()\n",
    "        for i in range(len(newList)):\n",
    "            if not dp or newList[i][1] > dp[-1][1]:\n",
    "                dp.append(newList[i])\n",
    "            else:\n",
    "                l = 0\n",
    "                r = len(dp) - 1\n",
    "                while l < r:\n",
    "                    mid = (r + l) // 2\n",
    "                    if newList[i][1] <= dp[mid][1]:\n",
    "                        r = mid\n",
    "                    else:\n",
    "                        l = mid + 1\n",
    "                dp[l] = newList[i]\n",
    "        return len(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "       \n",
    "        stack=[]\n",
    "        for _,w in sorted([h,-w] for h, w in zip(height,weight)):\n",
    "            w=-w\n",
    "            if not stack or stack[-1]<w:\n",
    "                stack.append(w)\n",
    "            else:\n",
    "                idx=bisect.bisect_left(stack,w)\n",
    "                stack[idx]=w\n",
    "        return len(stack)\n",
    "\n",
    "\n",
    "\n",
    "# [Python3] 9行 和354题俄罗斯套娃一样 先按height排序 再找weight的最长递增序列\n",
    "# 作者：Justin Yuan\n",
    "# 链接：https://leetcode.cn/problems/circus-tower-lcci/solutions/335693/python3-he-354ti-e-luo-si-tao-wa-yi-yang-an-height/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        per=[]\n",
    "        for w,h in zip(height,weight):\n",
    "            per.append([w,h])\n",
    "\n",
    "        per=sorted(per,key=lambda x:[x[0],-x[1]])\n",
    "        dp=[per[0][1]]\n",
    "        for i in range(1,len(height)):\n",
    "            if per[i][1]>dp[-1]:\n",
    "                dp.append(per[i][1])\n",
    "            else:\n",
    "                left,right=0,len(dp)-1\n",
    "                while left<right:\n",
    "                    mid=(left+right)//2\n",
    "                    if per[i][1]<=dp[mid]:\n",
    "                        right=mid\n",
    "                    else:\n",
    "                        left=mid+1\n",
    "                dp[left]=per[i][1]\n",
    "\n",
    "\n",
    "        return len(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        length = len(height)\n",
    "        sorted_index_list = [0] * length\n",
    "        for index in range(length):\n",
    "            sorted_index_list[index] = index \n",
    "        sorted_index_list.sort(key=lambda index:[-height[index], weight[index]])\n",
    "        dp_list = [sorted_index_list[0]]\n",
    "        for index in sorted_index_list[1:]:\n",
    "            if weight[dp_list[-1]] > weight[index]:\n",
    "                dp_list.append(index)\n",
    "            else:\n",
    "                insert_index = binarySearch(dp_list, weight, index)\n",
    "                dp_list[insert_index] = index\n",
    "        return len(dp_list)\n",
    "\n",
    "def binarySearch(dp_list, weight, index):\n",
    "    left = 0 \n",
    "    right = len(dp_list) - 1\n",
    "    answer = -1  \n",
    "    while left <= right:\n",
    "        mid = (left + right) // 2\n",
    "        if weight[dp_list[mid]] > weight[index]:\n",
    "            answer = mid + 1\n",
    "            left = mid + 1 \n",
    "        else:\n",
    "            answer = mid \n",
    "            right = mid - 1\n",
    "    return answer \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self,mmin:int, mmax:int,val: int=0):\n",
    "        self.val = val\n",
    "        self.mmin = mmin\n",
    "        self.mmax = mmax \n",
    "        self.left = None \n",
    "        self.right = None \n",
    "\n",
    "    def myRepr(self,skip=0):\n",
    "        ss = ' '*skip\n",
    "        ss += '['+str(self.mmin)+','+str(self.mmax)+']'+':'+str(self.val)+'\\n'\n",
    "        if self.left != None:\n",
    "            ss += self.left.myRepr(skip+2)\n",
    "        if self.right != None:\n",
    "            ss += self.right.myRepr(skip+2)\n",
    "        return ss \n",
    "\n",
    "    def __repr__(self):\n",
    "        return self.myRepr()\n",
    "\n",
    "\n",
    "class LineTree:\n",
    "    def __init__(self,n:int):\n",
    "        self.length = n  \n",
    "        self.root = self.generate(0,n-1)\n",
    "\n",
    "    def __repr__(self):\n",
    "        return self.root.__repr__()\n",
    "\n",
    "    def generate(self,left,right) -> TreeNode:\n",
    "        # 生成一颗线段树\n",
    "        if left>right:\n",
    "            return None \n",
    "        root = TreeNode(left,right)\n",
    "        if left == right:\n",
    "            return root \n",
    "        mid = (left+right)//2 \n",
    "        root.left = self.generate(left, mid)\n",
    "        root.right = self.generate(mid+1, right)\n",
    "        return root \n",
    "\n",
    "    def myPush(self,root:TreeNode,x:int, val:int) -> int:\n",
    "        '''\n",
    "        插入一个点，更新最大值\n",
    "        '''\n",
    "        if root==None:\n",
    "            return 0\n",
    "        if x<root.mmin or x>root.mmax:\n",
    "            return root.val \n",
    "        if x==root.mmin and x==root.mmax:\n",
    "            root.val = max(root.val,val)\n",
    "        else:\n",
    "            p = self.myPush(root.left,x,val)\n",
    "            q = self.myPush(root.right,x,val) \n",
    "            root.val = max(p,q) \n",
    "        return root.val\n",
    "\n",
    "    def push(self,x:int, v:int):\n",
    "        self.myPush(self.root,x,v)\n",
    "\n",
    "    def myGotIt(self,root:TreeNode,left:int,right:int) -> int:\n",
    "        '''\n",
    "        获取left->right区间内的最大值\n",
    "        '''\n",
    "        if root==None:\n",
    "            return 0\n",
    "        if right<root.mmin or left>root.mmax:\n",
    "            return 0 \n",
    "        if left<=root.mmin and right>=root.mmax:\n",
    "            return root.val  \n",
    "        p = self.myGotIt(root.left, left, right)\n",
    "        q = self.myGotIt(root.right, left, right) \n",
    "        return max(p,q) \n",
    "\n",
    "    def gotIt(self,k:int) -> int:\n",
    "        '''\n",
    "        获取区间 [k:] 对应的最大值\n",
    "        '''\n",
    "        return self.myGotIt(self.root,k,self.length-1)\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        if len(height)<2:\n",
    "            return len(height)\n",
    "        # 将w映射到 0 - 10000 之间\n",
    "        ss = set()\n",
    "        for w in weight:\n",
    "            ss.add(w)\n",
    "        people = list(ss)\n",
    "        people.sort()\n",
    "        d = {}\n",
    "        num_weights = len(people)\n",
    "        for i,x in enumerate(people):\n",
    "            d[x] = num_weights-1-i \n",
    "        nums = [(h,d[w]) for h,w in zip(height,weight)]\n",
    "        nums.sort()  \n",
    "        dp = LineTree(len(people))\n",
    "        # 对 w 进行dp\n",
    "        mmax = 0\n",
    "        for i, (h,k) in enumerate(nums):\n",
    "            if k+1 == len(people):\n",
    "                # 重量是马戏团里最轻的 \n",
    "                dp.push(k,1)\n",
    "                continue \n",
    "            # 应该是这一步 dp[k+1:] 超时了，用个线段树把它替换掉 \n",
    "            v = dp.gotIt(k+1)\n",
    "            dp.push(k,v+1) \n",
    "        # print(dp)\n",
    "        return dp.gotIt(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "\n",
    "        def cmp(a,b) :\n",
    "            if a[0] == b[0] :\n",
    "                return  b[1] - a[1]\n",
    "            return a[0] - b[0]\n",
    "\n",
    "        hw = list(zip(height,weight))\n",
    "        hw.sort(key = cmp_to_key(cmp))\n",
    "        arr = []\n",
    "        for h,w in hw :\n",
    "            l,r = 0,len(arr)\n",
    "            while l < r :\n",
    "                mid = (l + r ) >> 1\n",
    "                if arr[mid] >= w :\n",
    "                    r = mid\n",
    "                else :\n",
    "                    l = mid + 1\n",
    "            if l == len(arr) :\n",
    "                arr.append(w)\n",
    "            else :\n",
    "                arr[l] = w\n",
    "        return len(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        n = len(height)\n",
    "        acc = [(h,w) for h,w in zip(height,weight)]\n",
    "        acc.sort(key=lambda c:(c[0],-c[1]))\n",
    "        res = [acc[0][1]]\n",
    "        for i in range(1,n):\n",
    "            if acc[i][1]>res[-1]:\n",
    "                res.append(acc[i][1])\n",
    "            else:\n",
    "                l,r = 0,len(res)-1\n",
    "                while l<=r:\n",
    "                    mid = (l+r)//2\n",
    "                    if res[mid]<acc[i][1]:\n",
    "                        l += 1\n",
    "                    else:\n",
    "                        r -= 1\n",
    "                res[l] = acc[i][1]\n",
    "        \n",
    "        return len(res)\n",
    "\n",
    "\n",
    "        # n = len(height)\n",
    "        # @cache\n",
    "        # def dfs(h,w):\n",
    "        #     tmp = [(height[i],weight[i]) for i in range(n) if height[i]<h and weight[i]<w]\n",
    "        #     if not tmp:return 1\n",
    "        #     return max(dfs(h0,w0) for h0,w0 in tmp)+1\n",
    "        # return max(dfs(height[i],weight[i]) for i in range(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        # n = len(height)\n",
    "        # f = [1] * n\n",
    "        # arr = sorted([x, y] for x, y in zip(height, weight))\n",
    "        # for i in range(1, n):\n",
    "        #     for j in range(i):\n",
    "        #         if arr[i][0] == arr[j][0]:\n",
    "        #             continue\n",
    "        #         if arr[i][1] < arr[j][1]:\n",
    "        #             f[i] = max(f[i], f[j] + 1)\n",
    "        # return max(f)\n",
    "\n",
    "        n = len(height)\n",
    "        arr = sorted(zip(height, weight), key=lambda x: (x[0], -x[1]))\n",
    "        ans = []\n",
    "        for x, y in arr:\n",
    "            i = bisect_left(ans, y)\n",
    "            ans[i:i+1] = [y]\n",
    "        return len(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        n = len(height)\n",
    "        acc = [(h,w) for h,w in zip(height,weight)]\n",
    "        acc.sort(key=lambda c:(c[0],-c[1]))\n",
    "        res = [acc[0][1]]\n",
    "        for i in range(1,n):\n",
    "            tmp = acc[i][1]\n",
    "            if tmp>res[-1]:\n",
    "                res.append(tmp)\n",
    "            else:\n",
    "                l,r = 0,len(res)-1\n",
    "                while l<=r:\n",
    "                    mid = (l+r)//2\n",
    "                    if res[mid]<tmp:\n",
    "                        l += 1\n",
    "                    else:\n",
    "                        r -= 1\n",
    "                res[l] = tmp\n",
    "        return len(res)\n",
    "\n",
    "\n",
    "        # n = len(height)\n",
    "        # @cache\n",
    "        # def dfs(h,w):\n",
    "        #     tmp = [(height[i],weight[i]) for i in range(n) if height[i]<h and weight[i]<w]\n",
    "        #     if not tmp:return 1\n",
    "        #     return max(dfs(h0,w0) for h0,w0 in tmp)+1\n",
    "        # return max(dfs(height[i],weight[i]) for i in range(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        newList = list()\n",
    "        for i in range(len(height)):\n",
    "            newList.append([height[i], weight[i]])\n",
    "        newList.sort(key=lambda x:[x[0], -x[1]])\n",
    "        print(newList)\n",
    "        dp = list()\n",
    "        for i in range(len(newList)):\n",
    "            if not dp or newList[i][1] > dp[-1][1]:\n",
    "                dp.append(newList[i])\n",
    "            else:\n",
    "                l = 0\n",
    "                r = len(dp) - 1\n",
    "                while l < r:\n",
    "                    mid = (r + l) // 2\n",
    "                    if newList[i][1] <= dp[mid][1]:\n",
    "                        r = mid\n",
    "                    else:\n",
    "                        l = mid + 1\n",
    "                dp[l] = newList[i]\n",
    "        return len(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        n=len(weight)\n",
    "        a=[(height[i],weight[i]) for i in range(n)]\n",
    "        a.sort(key=lambda x:(x[0],-x[1]))\n",
    "        print(a)\n",
    "        l=[a[i][1] for i in range(n)]\n",
    "        sl=SortedList()\n",
    "        for i in range(n):\n",
    "            if sl and l[i]<=sl[-1]:\n",
    "                del sl[sl.bisect_left(l[i])]\n",
    "            sl.add(l[i])\n",
    "        return len(sl)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        n = len(height)\n",
    "        acc = [(h,w) for h,w in zip(height,weight)]\n",
    "        acc.sort(key=lambda c:(c[0],-c[1]))\n",
    "        res = [acc[0][1]]\n",
    "        for i in range(1,n):\n",
    "            tmp = acc[i][1]\n",
    "            if tmp>res[-1]:\n",
    "                res.append(tmp)\n",
    "            else:\n",
    "                l,r = 0,len(res)-1\n",
    "                while l<=r:\n",
    "                    mid = (l+r)//2\n",
    "                    if res[mid]<tmp:\n",
    "                        l += 1\n",
    "                    else:\n",
    "                        r -= 1\n",
    "                res[l] = tmp\n",
    "        return len(res)\n",
    "\n",
    "\n",
    "        # n = len(height)\n",
    "        # @cache\n",
    "        # def dfs(h,w):\n",
    "        #     tmp = [(height[i],weight[i]) for i in range(n) if height[i]<h and weight[i]<w]\n",
    "        #     if not tmp:return 1\n",
    "        #     return max(dfs(h0,w0) for h0,w0 in tmp)+1\n",
    "        # return max(dfs(height[i],weight[i]) for i in range(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        people = [(h, w) for h, w in zip(height, weight)]\n",
    "        # 体重必须严格降序排列\n",
    "        people.sort(key=lambda p: (p[0], -p[1]))\n",
    "        # top[i]: 高度为i + 1的人堆的底部的人的最小重量\n",
    "        # 按照top数组的维护方式和定义, 即使people数组不按照重量排序一定是严格递减的\n",
    "        # 但是本题必须把people按照人的重量排序(且高度相同时按照体重降序排列)才能通过\n",
    "        bottom = [people[0][1]]\n",
    "        for p in people[1:]:\n",
    "            i = bisect.bisect_left(bottom, p[1])\n",
    "            if i == len(bottom):\n",
    "                # 在底部插入一个更重的人, 按照题意还需要保证这个人的\n",
    "                # 身高比之前的人严格更高. 由于people本身按照身高升序\n",
    "                # 排列, 这个人的身高不会低于前面的人. 身高相等时people\n",
    "                # 按照体重降序排列(体重大的排在前面), 所以只可能是身高\n",
    "                # 不相等而是严格更高.\n",
    "                bottom.append(p[1])\n",
    "            else:\n",
    "                bottom[i] = p[1]\n",
    "        return len(bottom)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "            # 二分\n",
    "        new_sort = sorted(zip(height,weight),key=lambda x:(x[0],-x[1]))\n",
    "        dp = []\n",
    "        for a,b in new_sort:\n",
    "            pos = bisect_left(dp,b)\n",
    "            dp[pos:pos+1] =[b]\n",
    "        return len(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        n = len(height)\n",
    "        acc = [(h,w) for h,w in zip(height,weight)]\n",
    "        acc.sort(key=lambda c:(c[0],-c[1]))\n",
    "        res = [acc[0][1]]\n",
    "        for i in range(1,n):\n",
    "            tmp = acc[i][1]\n",
    "            if tmp>res[-1]:\n",
    "                res.append(tmp)\n",
    "            else:\n",
    "                l,r = 0,len(res)-1\n",
    "                while l<=r:\n",
    "                    mid = (l+r)//2\n",
    "                    if res[mid]<tmp:\n",
    "                        l += 1\n",
    "                    else:\n",
    "                        r -= 1\n",
    "                res[l] = tmp\n",
    "        return len(res)\n",
    "\n",
    "\n",
    "        # n = len(height)\n",
    "        # @cache\n",
    "        # def dfs(h,w):\n",
    "        #     tmp = [(height[i],weight[i]) for i in range(n) if height[i]<h and weight[i]<w]\n",
    "        #     if not tmp:return 1\n",
    "        #     return max(dfs(h0,w0) for h0,w0 in tmp)+1\n",
    "        # return max(dfs(height[i],weight[i]) for i in range(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "\n",
    "        def cmp(a,b) :\n",
    "            if a[0] == b[0] :\n",
    "                return  b[1] - a[1]\n",
    "            return a[0] - b[0]\n",
    "\n",
    "        hw = list(zip(height,weight))\n",
    "        hw.sort(key = cmp_to_key(cmp))\n",
    "        print(hw)\n",
    "        arr = []\n",
    "        for h,w in hw :\n",
    "            l,r = 0,len(arr)\n",
    "            while l < r :\n",
    "                mid = (l + r ) >> 1\n",
    "                if arr[mid] >= w :\n",
    "                    r = mid\n",
    "                else :\n",
    "                    l = mid + 1\n",
    "            if l == len(arr) :\n",
    "                arr.append(w)\n",
    "            else :\n",
    "                arr[l] = w\n",
    "        return len(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        n = len(height)\n",
    "        acc = [(h,w) for h,w in zip(height,weight)]\n",
    "        acc.sort(key=lambda c:(c[0],-c[1]))\n",
    "        res = []\n",
    "        for h,w in acc:\n",
    "            if not res or w>res[-1]:\n",
    "                res.append(w)\n",
    "            else:\n",
    "                l,r = 0,len(res)-1\n",
    "                while l<=r:\n",
    "                    mid = (l+r)//2\n",
    "                    if res[mid]<w:\n",
    "                        l = mid+1\n",
    "                    else:\n",
    "                        r = mid-1\n",
    "                res[l] = w\n",
    "        return len(res)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        people = list(zip(height, weight))\n",
    "        n = len(people)\n",
    "        people.sort(key=lambda ele: (ele[0], -ele[1]))\n",
    "        dp = [people[0][1]]\n",
    "        for i in range(1, n):\n",
    "            if people[i][1] > dp[-1]:\n",
    "                dp.append(people[i][1])\n",
    "                continue\n",
    "            index = bisect.bisect_left(dp, people[i][1])\n",
    "            dp[index] = people[i][1]\n",
    "        return len(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        n=len(height)\n",
    "        temp=[(height[i],weight[i]) for i in range(n)]\n",
    "        temp=sorted(temp,key=lambda x:(x[0],-x[1]))\n",
    "        res = [temp[0][1]]\n",
    "        for t in temp[1:]:\n",
    "            if t[1]>res[-1]:\n",
    "                res.append(t[1])\n",
    "            else:\n",
    "                index = bisect_left(res,t[1])\n",
    "                res[index]=t[1]\n",
    "        return len(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        n = len(height)\n",
    "        acc = [(h,w) for h,w in zip(height,weight)]\n",
    "        acc.sort(key=lambda c:(c[0],-c[1]))\n",
    "        res = []\n",
    "        for h,w in acc:\n",
    "            if not res or w>res[-1]:\n",
    "                res.append(w)\n",
    "            else:\n",
    "                l,r = 0,len(res)-1\n",
    "                while l<=r:\n",
    "                    mid = (l+r)//2\n",
    "                    if res[mid]<w:\n",
    "                        l = mid+1\n",
    "                    else:\n",
    "                        r = mid-1\n",
    "                res[l] = w\n",
    "        return len(res)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        n = len(height)\n",
    "        acc = [(h,w) for h,w in zip(height,weight)]\n",
    "        acc.sort(key=lambda c:(c[0],-c[1]))\n",
    "        res = []\n",
    "        for h,w in acc:\n",
    "            if not res or w>res[-1]:\n",
    "                res.append(w)\n",
    "            else:\n",
    "                l,r = 0,len(res)-1\n",
    "                while l<=r:\n",
    "                    mid = (l+r)//2\n",
    "                    if res[mid]<w:\n",
    "                        l = mid+1\n",
    "                    else:\n",
    "                        r = mid-1\n",
    "                res[l] = w\n",
    "        return len(res)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        n = len(height)\n",
    "        acc = [(h,w) for h,w in zip(height,weight)]\n",
    "        acc.sort(key=lambda c:(c[0],-c[1]))\n",
    "        res = [acc[0][1]]\n",
    "        for i in range(1,n):\n",
    "            if acc[i][1]>res[-1]:\n",
    "                res.append(acc[i][1])\n",
    "            else:\n",
    "                l,r = 0,len(res)-1\n",
    "                while l<=r:\n",
    "                    mid = (l+r)//2\n",
    "                    if res[mid]<acc[i][1]:\n",
    "                        l += 1\n",
    "                    else:\n",
    "                        r -= 1\n",
    "                res[l] = acc[i][1]\n",
    "        return len(res)\n",
    "\n",
    "\n",
    "        # n = len(height)\n",
    "        # @cache\n",
    "        # def dfs(h,w):\n",
    "        #     tmp = [(height[i],weight[i]) for i in range(n) if height[i]<h and weight[i]<w]\n",
    "        #     if not tmp:return 1\n",
    "        #     return max(dfs(h0,w0) for h0,w0 in tmp)+1\n",
    "        # return max(dfs(height[i],weight[i]) for i in range(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        n = len(height)\n",
    "        acc = [(height[i],weight[i]) for i in range(n)]\n",
    "        acc.sort(key=lambda c:(c[0],-c[1]))\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            tmp = acc[i][1]\n",
    "            if not res or tmp>res[-1]:\n",
    "                res.append(tmp)\n",
    "            else:\n",
    "                l,r = 0,len(res)-1\n",
    "                while l<=r:\n",
    "                    mid = (l+r)//2\n",
    "                    if res[mid]<tmp:\n",
    "                        l = mid+1\n",
    "                    else:\n",
    "                        r = mid-1\n",
    "                res[l] = tmp\n",
    "        return len(res)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[1,2,3,4]\n",
    "[4,3,2,1]\n",
    "\n",
    "[65,70,56,75,60,68]\n",
    "[100,150,90,190,95,110]\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        peop = sorted(zip(height, weight), key=lambda x: (x[0], -x[1]))\n",
    "        return self.longestInc([w for _, w in peop])\n",
    "    def longestInc(self, weights):\n",
    "        dp = []\n",
    "        for w in weights:\n",
    "            l = self.bisectLeft(dp, w)\n",
    "            if l == len(dp):\n",
    "                dp.append(w)\n",
    "            else:\n",
    "                dp[l] = w\n",
    "        return len(dp)\n",
    "    def bisectLeft(self, dp, w):\n",
    "        l, r = 0, len(dp)\n",
    "        while l < r:\n",
    "            m = l + ((r-l) >> 1)\n",
    "            if dp[m] < w:\n",
    "                l = m+1\n",
    "            else:\n",
    "                r = m\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        n = len(height)\n",
    "        acc = [(h,w) for h,w in zip(height,weight)]\n",
    "        acc.sort(key=lambda c:(c[0],-c[1]))\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            tmp = acc[i][1]\n",
    "            if not res or tmp>res[-1]:\n",
    "                res.append(tmp)\n",
    "            else:\n",
    "                l,r = 0,len(res)-1\n",
    "                while l<=r:\n",
    "                    mid = (l+r)//2\n",
    "                    if res[mid]<tmp:\n",
    "                        l = mid+1\n",
    "                    else:\n",
    "                        r = mid-1\n",
    "                res[l] = tmp\n",
    "        return len(res)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        n = len(height)\n",
    "        acc = [(height[i],weight[i]) for i in range(n)]\n",
    "        acc.sort(key=lambda c:(c[0],-c[1]))\n",
    "        res = [acc[0][1]]\n",
    "        for i in range(1,n):\n",
    "            tmp = acc[i][1]\n",
    "            if tmp>res[-1]:\n",
    "                res.append(tmp)\n",
    "            else:\n",
    "                l,r = 0,len(res)-1\n",
    "                while l<=r:\n",
    "                    mid = (l+r)//2\n",
    "                    if res[mid]<tmp:\n",
    "                        l += 1\n",
    "                    else:\n",
    "                        r -= 1\n",
    "                res[l] = tmp\n",
    "        return len(res)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        # 最长递增子序列的二维版本\n",
    "        # 注意排序时按照第一升序，第二降序即可\n",
    "        n = len(height)\n",
    "        rec = [(height[i], weight[i]) for i in range(n)]\n",
    "        rec.sort(key=lambda x:(x[0], -x[1]))\n",
    "        res = [rec[0]]\n",
    "        \n",
    "        for i in range(1,n):\n",
    "            cur = rec[i]\n",
    "            if cur[1]>res[-1][1]:\n",
    "                res.append(cur)\n",
    "            else:\n",
    "                idx = bisect_left(res, cur[1], key=lambda x:x[1])\n",
    "                res[idx] = cur\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        li = []\n",
    "        for i, j in zip(height, weight):\n",
    "            li.append([i, j])\n",
    "        li.sort(key=lambda x: (x[0], -x[1]))\n",
    "\n",
    "        nums = [i[1] for i in li]\n",
    "        dp = []\n",
    "        for i in range(len(nums)):\n",
    "            # 如果新数比末尾数大，直接append\n",
    "            if not dp or nums[i] > dp[-1]:\n",
    "                dp.append(nums[i])\n",
    "            # 如果新数没有末尾数大，寻找第一个比新数小的数d[k]，并更新d[k+1] = nums[i]\n",
    "            left, right = 0, len(dp) - 1\n",
    "            while left <= right:\n",
    "                mid = (left + right) // 2\n",
    "                if dp[mid] >= nums[i]:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            if left < len(dp):\n",
    "                dp[left] = nums[i]\n",
    "\n",
    "        return len(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        li = []\n",
    "        for i, j in zip(height, weight):\n",
    "            li.append([i,j])\n",
    "        li.sort(key = lambda x:(x[0],-x[1]))\n",
    "\n",
    "        nums = [i[1] for i in li]\n",
    "        dp = []\n",
    "        for i in range(len(nums)):\n",
    "            # 如果新数比末尾数大，直接append\n",
    "            if not dp or nums[i]>dp[-1]:\n",
    "                dp.append(nums[i])\n",
    "            # 如果新数没有末尾数大，寻找第一个比新数小的数d[k]，并更新d[k+1] = nums[i]\n",
    "            left, right = 0, len(dp)-1\n",
    "            while left <= right:\n",
    "                mid = (left + right) // 2\n",
    "                if dp[mid] >= nums[i]:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            if left < len(dp):\n",
    "                dp[left] = nums[i]\n",
    "\n",
    "        return len(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        li = []\n",
    "        for i, j in zip(height, weight):\n",
    "            li.append([i, j])\n",
    "        li.sort(key=lambda x: (x[0], -x[1]))\n",
    "\n",
    "        nums = [i[1] for i in li]\n",
    "        dp = []\n",
    "        for i in range(len(nums)):\n",
    "            if not dp or nums[i] > dp[-1]:\n",
    "                dp.append(nums[i])\n",
    "            else:\n",
    "                left, right = 0, len(dp) - 1\n",
    "                while left <= right:\n",
    "                    mid = (left + right) // 2\n",
    "                    if dp[mid] >= nums[i]:\n",
    "                        right = mid - 1\n",
    "                    else:\n",
    "                        left = mid + 1\n",
    "                dp[left] = nums[i]\n",
    "        return len(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    import bisect\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:       \n",
    "       dp=[]\n",
    "       for a,b in sorted(zip(height,weight),key = lambda x:[x[0],-x[1]]):\n",
    "           pos = bisect.bisect_left(dp,b)\n",
    "           dp[pos:pos+1] = [b]\n",
    "       return len(dp)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    import bisect\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:       \n",
    "       dp=[]\n",
    "       for a,b in sorted(zip(height,weight),key = lambda x:[x[0],-x[1]]):\n",
    "           pos = bisect.bisect_left(dp,b)\n",
    "           dp[pos:pos+1] = [b]\n",
    "       return len(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        temp_list = []\n",
    "        for h, w in zip(height,weight):\n",
    "            temp_list.append([h, w])\n",
    "        temp_list.sort(key=lambda x:(x[0], -x[1]))\n",
    "        new_weight = [num[1] for num in temp_list]\n",
    "        dp = []\n",
    "        for num in new_weight:\n",
    "            if not dp or num > dp[-1]:\n",
    "                dp.append(num)\n",
    "            elif num == dp[-1]:\n",
    "                continue\n",
    "            else:\n",
    "                left, right = 0, len(dp)-1\n",
    "                while left <= right:\n",
    "                    mid = (left+right) // 2\n",
    "                    if dp[mid] >= num:\n",
    "                        right = mid - 1\n",
    "                    else:\n",
    "                        left = mid + 1\n",
    "                dp[left] = num\n",
    "        return len(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        newList = list()\n",
    "        for i in range(len(height)):\n",
    "            newList.append([height[i], weight[i]])\n",
    "        newList.sort(key=lambda x:[x[0], -x[1]])\n",
    "        dp = list()\n",
    "        for i in range(len(newList)):\n",
    "            if not dp or newList[i][1] > dp[-1][1]:\n",
    "                dp.append(newList[i])\n",
    "            else:\n",
    "                l = 0\n",
    "                r = len(dp) - 1\n",
    "                while l < r:\n",
    "                    mid = (r + l) // 2\n",
    "                    if newList[i][1] <= dp[mid][1]:\n",
    "                        r = mid\n",
    "                    else:\n",
    "                        l = mid + 1\n",
    "                dp[l] = newList[i]\n",
    "        return len(dp)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        dp = []\n",
    "        for h,w in sorted(zip(height,weight),key=lambda x:[x[0],-x[1]]):\n",
    "            pos = bisect_left(dp,w)\n",
    "            # dp[pos:pos+1]=[w]\n",
    "            if pos < len(dp):\n",
    "                dp[pos] = w\n",
    "            else:\n",
    "                dp.append(w)\n",
    "        return len(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        # 一个身高只保留一个体重，新数据只有替换和新增\n",
    "        import bisect\n",
    "\n",
    "\n",
    "        dp = list()\n",
    "        for cur_height, cur_weight in sorted(zip(height,weight),key = lambda x:[x[0],-x[1]]):\n",
    "            \n",
    "            #因为weight降序，当cur_weight > dp[-1][1]，cur_height必然> dp[-1][0]\n",
    "            if not dp or cur_weight > dp[-1][1]:\n",
    "                dp.append((cur_height, cur_weight))\n",
    "            else:\n",
    "                l = 0\n",
    "                r = len(dp) - 1\n",
    "                while l < r:\n",
    "                    mid = (r + l) // 2\n",
    "                    if cur_weight <= dp[mid][1]:\n",
    "                        r = mid\n",
    "                    else:\n",
    "                        l = mid + 1\n",
    "                dp[l] = (cur_height, cur_weight)\n",
    "        return len(dp)\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        hw = [[height[i], weight[i]] for i in range(len(weight))]\n",
    "        hw = sorted(hw, key=lambda x: (x[0], -x[1]))\n",
    "        stack = []\n",
    "        for h, w in hw:  # 身高已经是升序了，排体重就可以\n",
    "            if not stack:\n",
    "                stack.append(w)\n",
    "            else:\n",
    "                if stack[-1] < w:  # 栈顶小于 w，直接入栈\n",
    "                    stack.append(w)\n",
    "                else:\n",
    "                    idx = self.bisect_left(stack, w)\n",
    "                    stack[idx] = w \n",
    "        \n",
    "        return len(stack)\n",
    "\n",
    "    def bisect_left(self, arr: List, target: int) -> int:\n",
    "        left = 0\n",
    "        right = len(arr) - 1 \n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2 \n",
    "            if arr[mid] == target:\n",
    "                right = mid - 1 \n",
    "            elif arr[mid] > target:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1 \n",
    "        return left "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    import bisect\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        dp=[]\n",
    "        for a,b in sorted(zip(height,weight),key = lambda x:[x[0],-x[1]]):\n",
    "           pos = bisect.bisect_left(dp,b)\n",
    "           dp[pos:pos+1] = [b]\n",
    "        return len(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    import bisect\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:       \n",
    "       dp=[]\n",
    "       for a,b in sorted(zip(height,weight),key = lambda x:[x[0],-x[1]]):\n",
    "           pos = bisect.bisect_left(dp,b)\n",
    "           dp[pos:pos+1] = [b]\n",
    "       return len(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        hw = [[height[i], weight[i]] for i in range(len(weight))]\n",
    "        hw = sorted(hw, key=lambda x: (x[0], -x[1]))\n",
    "        stack = []\n",
    "        for h, w in hw:  # 身高已经是升序了，排体重就可以\n",
    "            if not stack:\n",
    "                stack.append(w)\n",
    "            else:\n",
    "                if stack[-1] < w:  # 栈顶小于 w，直接入栈\n",
    "                    stack.append(w)\n",
    "                else:\n",
    "                    idx = self.bisect_left(stack, w)\n",
    "                    stack[idx] = w \n",
    "        \n",
    "        return len(stack)\n",
    "\n",
    "    def bisect_left(self, arr: List, target: int) -> int:\n",
    "        left = 0\n",
    "        right = len(arr) - 1 \n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2 \n",
    "            if arr[mid] >= target:\n",
    "                right = mid - 1 \n",
    "            else:\n",
    "                left = mid + 1 \n",
    "        return left "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        List1 = list()\n",
    "        for i in range(len(height)):\n",
    "            List1.append([height[i], weight[i]])\n",
    "        List1.sort(key=lambda x:[x[0], -x[1]])\n",
    "        res = list()\n",
    "        for i in range(len(List1)):\n",
    "            if not res or List1[i][1] > res[-1][1]:\n",
    "                res.append(List1[i])\n",
    "            else:\n",
    "                l = 0\n",
    "                r = len(res) - 1\n",
    "                while l < r:\n",
    "                    mid = (r + l) // 2\n",
    "                    if List1[i][1] <= res[mid][1]:\n",
    "                        r = mid\n",
    "                    else:\n",
    "                        l = mid + 1\n",
    "                res[l] = List1[i]\n",
    "        return len(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        hw = [[height[i], weight[i]] for i in range(len(weight))]\n",
    "        hw = sorted(hw, key=lambda x: (x[0], -x[1]))\n",
    "        stack = []\n",
    "        for h, w in hw:  # 身高已经是升序了，排体重就可以\n",
    "            if not stack:\n",
    "                stack.append(w)\n",
    "            else:\n",
    "                if stack[-1] < w:  # 栈顶小于 w，直接入栈\n",
    "                    stack.append(w)\n",
    "                else:\n",
    "                    idx = self.bisect_left(stack, w)\n",
    "                    stack[idx] = w \n",
    "        \n",
    "        return len(stack)\n",
    "\n",
    "    def bisect_left(self, arr: List, target: int) -> int:\n",
    "        left = 0\n",
    "        right = len(arr) - 1 \n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2 \n",
    "            if arr[mid] < target:\n",
    "                left = mid + 1 \n",
    "            else:\n",
    "                right = mid - 1 \n",
    "        return left "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        hw = [[height[i], weight[i]] for i in range(len(weight))]\n",
    "        hw = sorted(hw, key=lambda x: (x[0], -x[1]))\n",
    "        stack = []\n",
    "        for h, w in hw:  # 身高已经是升序了，排体重就可以\n",
    "            if not stack:\n",
    "                stack.append(w)\n",
    "            else:\n",
    "                if stack[-1] < w:  # 栈顶小于 w，直接入栈\n",
    "                    stack.append(w)\n",
    "                else:\n",
    "                    idx = self.bisect_left(stack, w)\n",
    "                    stack[idx] = w \n",
    "        \n",
    "        return len(stack)\n",
    "\n",
    "    def bisect_left(self, arr: List, target: int) -> int:\n",
    "        left = 0\n",
    "        right = len(arr) - 1 \n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2 \n",
    "            if arr[mid] < target:\n",
    "                left = mid + 1 \n",
    "            else:\n",
    "                right = mid - 1 \n",
    "        return left "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        set1 = [[height[i], weight[i]] for i in range(len(height))]\n",
    "        set1 = sorted(set1, key = lambda x : [x[0], -x[1]])\n",
    "        # 此时看set[i][1]\n",
    "        ans = [set1[0][1]]\n",
    "        for i in range(1, len(set1)):\n",
    "            if set1[i][1] > ans[-1]:\n",
    "                ans.append(set1[i][1])\n",
    "            elif set1[i][1] == ans[-1]:\n",
    "                continue\n",
    "            elif set1[i][1] <= ans[0]:\n",
    "                ans[0] = set1[i][1]\n",
    "            else:\n",
    "                left, right = 0, len(ans) - 1\n",
    "                while left < right:\n",
    "                    mid = left + (right - left) // 2\n",
    "                    if ans[mid] >= set1[i][1]:\n",
    "                        right = mid\n",
    "                    elif ans[mid] < set1[i][1]:\n",
    "                        left = mid + 1\n",
    "                ans[left] = set1[i][1]\n",
    "        return len(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        hw = [[height[i], weight[i]] for i in range(len(weight))]\n",
    "        hw = sorted(hw, key=lambda x: (x[0], -x[1]))\n",
    "        stack = []\n",
    "        for h, w in hw:  # 身高已经是升序了，排体重就可以\n",
    "            if not stack:\n",
    "                stack.append(w)\n",
    "            else:\n",
    "                if stack[-1] < w:  # 栈顶小于 w，直接入栈\n",
    "                    stack.append(w)\n",
    "                else:\n",
    "                    idx = bisect.bisect_left(stack, w)\n",
    "                    stack[idx] = w \n",
    "        \n",
    "        return len(stack)\n",
    "\n",
    "    def bisect_left(self, arr: List, target: int) -> int:\n",
    "        left = 0\n",
    "        right = len(arr) - 1 \n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2 \n",
    "            if arr[mid] < target:\n",
    "                left = mid + 1 \n",
    "            else:\n",
    "                right = mid - 1 \n",
    "        return right "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        new = sorted(zip(height, weight), key=lambda x: (x[0], -x[1]))\n",
    "        print(new)\n",
    "        \n",
    "        n = len(new)\n",
    "        res = [new[0]]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            #print(res, res[-1][1], new[i][1])\n",
    "            if res[-1][1]<new[i][1]:\n",
    "                res.append(new[i])\n",
    "            else:\n",
    "                left, right = 0, len(res)-1\n",
    "\n",
    "                while left<=right:\n",
    "                    mid = (left+right)//2\n",
    "                    if res[mid][1]<new[i][1]:\n",
    "                        left = mid+1\n",
    "                    else:\n",
    "                        right = mid-1\n",
    "                \n",
    "                res[left]=new[i]\n",
    "            # print(res)\n",
    "        return len(res)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #理解成 高重理解为长宽， 求套最多层矩形的dp即可\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        n = len(height)\n",
    "        arr = [[0, 0] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            arr[i] = [height[i], weight[i]]\n",
    "        arr = sorted(arr, key = lambda x: (x[0], -x[1]))\n",
    "        # print(arr)\n",
    "        dp = []\n",
    "        curMax = 1\n",
    "        for i in range(n):\n",
    "            left, right = 0, len(dp)\n",
    "            if i == 0 or arr[i][1] > dp[-1]:\n",
    "                dp.append(arr[i][1])\n",
    "            else:\n",
    "                while left < right:\n",
    "                    mid = (left + right) // 2\n",
    "                    if dp[mid] < arr[i][1]:\n",
    "                        left = mid + 1\n",
    "                    else:\n",
    "                        right = mid\n",
    "                dp[left] = arr[i][1]\n",
    "                \n",
    "        return len(dp)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        \n",
    "        n = len(height)\n",
    "        jihe = []\n",
    "        for i in range(n):\n",
    "            jihe.append([height[i],weight[i]])\n",
    "        jihe.sort(key = lambda x:[x[0],-x[1]])\n",
    "        dp = []\n",
    "        for i in range(n):\n",
    "            if not dp or jihe[i][1] > dp[-1][1]:\n",
    "                dp.append(jihe[i])\n",
    "            else:\n",
    "                l = 0\n",
    "                r = len(dp) - 1\n",
    "                while l < r:\n",
    "                    mid = (l+r)//2\n",
    "                    if jihe[i][1] <= dp[mid][1]:\n",
    "                        r = mid\n",
    "                    else:\n",
    "                        l = mid + 1\n",
    "                \n",
    "                dp[l] = jihe[i]\n",
    "        return len(dp)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:\n",
    "        newlist = []\n",
    "        for i in range(len(height)):\n",
    "            newlist.append([height[i],weight[i]])\n",
    "        newlist.sort(key=lambda x:[x[0],-x[1]])\n",
    "        dp = []\n",
    "        for i in range(len(newlist)):\n",
    "            if not dp or newlist[i][1] > dp[-1][1]:\n",
    "                dp.append(newlist[i])\n",
    "            else:\n",
    "                l = 0\n",
    "                r = len(dp) - 1\n",
    "                while l < r:\n",
    "                    mid = (r+l)//2            \n",
    "                    if newlist[i][1] <= dp[mid][1]:\n",
    "                        r = mid\n",
    "                    else:\n",
    "                        l = mid + 1\n",
    "                dp[l] = newlist[i]\n",
    "        return len(dp)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
